//二叉树的创建
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
    if(*(a+(*pi)) == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode *treenode = (BTNode*)malloc(sizeof(BTNode));
    if(treenode == NULL)
    {
        perror("Tree malloc fail");
        exit(-1);
    }
    treenode->data = *(a+(*pi));
    (*pi)++;
    treenode->left = BinaryTreeCreate(a,pi);
    treenode->right = BinaryTreeCreate(a,pi);
    return treenode;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
    if(*root == NULL)
        return;
    BinaryTreeDestory(&(*root)->left);
    BinaryTreeDestory(&(*root)->right);
    free(*root);
    *root = NULL;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
    if(root == NULL)
        return 0;
    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    assert(k > 0);
    if(root == NULL)
        return 0;
    if(k == 1)
        return 1;
    return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if(root == NULL)
        return NULL;
    if(root->data == x)
        return root;

    BTNode* left = BinaryTreeFind(root->left,x);
    if(left)
        return left;
    BTNode* right = BinaryTreeFind(root->right,x);
    if(right)
        return right;

    return NULL;
}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
    if(root == NULL)
        return;
    printf("%c ",root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
    if(root == NULL)
        return;
    BinaryTreeInOrder(root->left);
    printf("%c ",root->data);
    BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
    if(root == NULL)
        return;
    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ",root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    Que q;
    QueueInit(&q);
    if(root == NULL)
        return;
    QueuePush(&q,root);
    while(!QueueEmpty(&q))
    {
        QDataType top = QueueFront(&q);
        printf("%c ",top->data);
        if(top->left)
            QueuePush(&q,top->left);
        if(top->right)
            QueuePush(&q,top->right);
        QueuePop(&q);
    }
    printf("\n");
    QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
    Que q;
    QueueInit(&q);
    if(root == NULL)
        return 0;
    QueuePush(&q,root);
    while(!QueueEmpty(&q))
    {
        QDataType top = QueueFront(&q);
        if(top == NULL)
            break;
        QueuePush(&q,top->left);
        QueuePush(&q,top->right);
        QueuePop(&q);
    }
    while (!QueueEmpty(&q))
    {
        if(QueueFront(&q) != NULL)
        {
            QueueDestroy(&q);
            return 0;
        }
        QueuePop(&q);
    }
    QueueDestroy(&q);
    return 1;
}
//二叉树的深度
int BinaryTreeHigh(BTNode* root)
{
    if(root == NULL)
        return 0;
    int left = BinaryTreeHigh(root->left);
    int right = BinaryTreeHigh(root->right);
    return (left>right ? left : right) + 1;
}
